/*
 * @Author: szx
 * @Date: 2022-05-06 15:16:04
 * @LastEditTime: 2022-05-06 15:35:59
 * @Description:
 * @FilePath: \leetcode\剑指offerII\112\112.js
 */
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function (matrix) {
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const m = matrix.length;
    const n = matrix[0].length;
    let res = 0;
    const maxArr = new Array(m).fill(0).map(() => new Array(n).fill(0));
    const dfs = (i, j) => {
        if (maxArr[i][j] != 0) return maxArr[i][j];
        ++maxArr[i][j];
        for (let dir of dirs) {
            const x = dir[0] + i;
            const y = dir[1] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                maxArr[i][j] = Math.max(dfs(x, y) + 1, maxArr[i][j]);
            }
        }
        return maxArr[i][j];
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            res = Math.max(res, dfs(i, j));
        }
    }
    return res;
};
